package hot_100;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Darven
 * @createTime: 2025-10-05  00:26
 * @description: TODO
 */
public class P17 {

    public static void main(String[] args) {
        P17 p17 = new P17();
        List<String> list = p17.letterCombinations("23");
        for (String s:list){
            System.out.println(s);
        }
    }

    private StringBuffer sb=new StringBuffer();

    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()){
            return null;
        }
        String[] cs=new String[10];
        cs[2]="abc";
        cs[3]="def";
        cs[4]="ghi";
        cs[5]="jkl";
        cs[6]="mno";
        cs[7]="pqrs";
        cs[8]="tuv";
        cs[9]="wxyz";
        List<String> ans=new ArrayList<>();
        dfs(digits,0,ans,cs);
        return ans;
    }

    private void dfs(String digits,int depth,List<String> ans,String[] cs){
        // 终止条件：当遍历完之后即可
        if(sb.length()==digits.length()){
            // 满足digits长度才能添加
            ans.add(new String(sb));
            return;
        }

        char c = digits.charAt(depth);
        int num=c-'0';
        String c1 = cs[num];
        // 组合，重复
        for (int i=0;i<c1.length();i++){
            // 先添加，
            sb.append(c1.charAt(i));
            // 递归
            dfs(digits, depth+1, ans, cs);
            // 回溯
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
